package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.
 * @author Adiy
 *
 */
public class LongestConsecutiveSequence {

	public static void main(String[] args){
		int nums[]={100, 4, 200, 1, 3, 2};
		int nums1[]={0};
		int nums2[]={0,0};
		int nums3[]={1,2,0,1};
		int nums4[]={9,1,4,7,3,-1,0,0,5,8,-1,6};
		int result=longestConsecutive(nums4);
		System.out.println(result);;
	}
	public static int longestConsecutive(int[] nums){
		 Arrays.sort(nums);
		 int i=0,len=nums.length;
		 if(len==0) return 0;
		 List<Integer> list=new ArrayList<Integer>();
		 int count=1;
	     for(i=0;i<len-1;i++){
	    	 if(nums[i]+1==nums[i+1]){
	    		 count+=1;
	    	 }else if(nums[i]+1<nums[i+1]){
	    		 list.add(count);
	    		 count=1;
	    	 }
	     }
	     list.add(count);
	     int max=list.get(0);
//	     for(int k=0;k<list.size();k++){
//	    	 if(list.get(k)>max)
//	    		 max=list.get(k);
//	     }
	     Iterator<Integer> it=list.iterator();
	     while(it.hasNext()){
	    	 int a=it.next();
	    	 if(a>max) max=a;
	     }
	     return max;
	}
}
